In graphics processing, the ability to render and fill polygons or images which are not blurred in an easy and efficient manner is important. Previously, various techniques for rendering and filling polygons have been implemented. These techniques include, for example, an Ordered Edge List algorithm and a Bresenham procedure, both of which are described in J. D. Foley et al., Fundamentals of Interactive Computer Graphics (1982). Many of the techniques known today render and fill polygons using a horizontal scan strategy. Others, use a vertical scan strategy.
One example of a filling technique using a horizontal scan technique is disclosed in U.S. Pat. No. 4,763,119, entitled "Image Processing System for Area Filling of Graphics," issued on Aug. 9, 1988 and assigned to International Business Machines, Corporation. In U.S. Pat. No. 4,763,119, an area fill technique for graphic images is disclosed, wherein the contour lines constituting an image are given in a series of line segments and horizontal line segments are ignored. The pixels of each line segment are stored in a work memory such that each line segment is represented by one pixel per horizontal line. An even number of contour line pixels exist in each horizontal line in the work memory and, area fill can be realized by scanning each horizontal line in the work memory and turning on pixel memory cells from an odd numbered contour line pixel to an even numbered contour line pixel.
In U.S. Pat. No. 4,626,838, entitled "Filled Shaped Generating Apparatus," issued on Dec. 2, 1986 and assigned to Hitachi, Ltd., an apparatus for filling an interior of a shape to be displayed on a raster scan CRT is disclosed. The apparatus includes a memory for storing information of starting points and ending points for filling. The write of a filling color code into the refresh memory is initiated and terminates in response to the filling starting point and ending point, respectively, but inhibited at its memory locations on the contour of the shape. The direction of the filling is perpendicular to the horizontal raster scanning of the CRT.
Many of the known rendering and filling techniques, especially those which are mostly hardware implemented, are not capable, however, of satisfying all of the known X Window EvenOdd fill rules, which are described in X Protocol Reference Manual for X Version 11, Volume 0 by O'Reilly and Associates, Inc. (May 1990), which is hereby incorporated by reference. In addition, some of the rendering techniques are mostly software implemented and require complex data structures which are difficult to use and reduce the processing speed. Since, in graphic processing, it is advantageous to satisfy the X EvenOdd Rules and it is imperative to render and fill the polygons in an expedient manner, there exists a need for a rendering and filling technique which uses vertical span architecture to render and fill polygon outlines.
In addition, a need exists for a polygon rendering and filling technique which is capable of using vertical spans and is faster and less complex than previously implemented methods. Further, there exists a need for a rendering and filling technique which is capable of using vertical spans and still conform to the X EvenOdd fill rules. Still further, a need exists for a method and system that uses vertical span strategy for rendering and filling polygons in which a pixel on the edge of a polygon is drawn if, and only if, the interior of the polygon is to the right of the pixel or below the pixel. A yet further need exists for a polygon rendering and filling technique which does not need complex data structures and is capable of being implemented mostly in hardware using vertical span architecture.